package demo_leetcode_day;

/*
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
提示：
输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class demo_20200804 {
    public static void main(String[] args) {
        System.out.println(new Solution().canFinish(4, new int[][]{
                {0,1},
                {1,2},
                {0,3},
                {3,0},
        }));
    }

    static class Solution {
        /**
         * 思路，实际上是各自的线条，需要判断是，是否存在走不通的死路，即判断是否存在组成闭合的线
         */
        Map<Integer, List<Integer>> mapLine = new HashMap<>(); // 线条
        NodeStatus[] arrNode = null; // 节点状态

        enum NodeStatus {
            UN, // 未处理
            ING, // 处理中
            ED // 已处理（通路）
        }

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            // 所有线条保存
            for (int i = 0; i < prerequisites.length; i++) {
                Integer keyA = prerequisites[i][0];
                Integer keyB = prerequisites[i][1];
                if (mapLine.containsKey(keyA)) {
                    mapLine.get(keyA).add(keyB);
                } else {
                    mapLine.put(keyA, new ArrayList<Integer>() {{
                        add(keyB);
                    }});
                }
            }
            // 节点初始化
            arrNode = new NodeStatus[numCourses];
            Arrays.fill(arrNode, NodeStatus.UN);
            // 节点遍历
            for (int i = 0; i < numCourses; i++) {
                if (arrNode[i] == NodeStatus.UN) {
                    if (isClose(i)) {
                        return false;
                    }
                }
            }
            return true;
        }

        // 判断是否闭合
        private boolean isClose(int i) {
            arrNode[i] = NodeStatus.ING; // 节点状态变为处理中
            if(!mapLine.containsKey(i)) {
                arrNode[i] = NodeStatus.ED;
                return false;
            }
            List<Integer> listNext = mapLine.get(i);
            // 是否闭合判断
//            int closeNode = 0;
            for (int j = 0; j < listNext.size(); j++) {
                // 对象节点是处理中，判断是闭合
                if(arrNode[listNext.get(j)] == NodeStatus.ING){
//                    closeNode++;
                    return true;
                }
                // 对象是未处理，则去处理
                if(arrNode[listNext.get(j)] == NodeStatus.UN && isClose(listNext.get(j))){
//                    closeNode++;
                    return true;
                }
            }
//            if (closeNode > 0 && closeNode == listNext.size()) return true;
            // 全部处理中节点状态变为完成
            arrNode[i] = NodeStatus.ED;
            return false;
        }
    }
}
